#pragma once

#include "GraphAlgorithms.h"
#include "StronglyConnectedComponentsGraph.h"
#include <string>
#include <stdexcept>
#include <map>

namespace{
	struct HashLexem{
		int firstHash, secondHash;
		bool isTrueFirst, isTrueSecond;
		HashLexem(){}
	};

	std::unique_ptr<Graph> buildSatGraph(const std::vector<HashLexem>& arguments, int numberOfArguments){
		/**
		*	Structure of SAT Graph:
		*	Vertices are numbered from 0 to 2*(num of variables in 2-SAT expression) - 1
		*	even vertexes respond to True variable
		*	odd vertexes respond to False variable
		*/
		std::vector<Edge> edgesList;
		int vertexNum = numberOfArguments << 1;
		for (auto currentLexem : arguments){
			int fromVertex = currentLexem.firstHash << 1;
			if (currentLexem.isTrueFirst){
				++fromVertex;
			}
			int toVertex = currentLexem.secondHash << 1;
			if (!currentLexem.isTrueSecond) {
				++toVertex;
			}
			edgesList.push_back({ fromVertex, toVertex });
			if (currentLexem.isTrueFirst){
				--fromVertex;
			}
			else{
				++fromVertex;
			}
			if (currentLexem.isTrueSecond){
				++toVertex;
			}
			else{
				--toVertex;
			}
			edgesList.push_back({ toVertex, fromVertex });
		}
		return readGraph(vertexNum, edgesList);
	}

	bool existsSatSolution(const std::vector<int>& componentsList){
		for (size_t currentVertex = 0; currentVertex < componentsList.size(); currentVertex += 2)
			if (componentsList[currentVertex] == componentsList[currentVertex + 1])
				return false;
		return true;
	}
	bool satFindingHashSolutions(int numberOfVariables, const std::vector<HashLexem>& listOfHashedLexems,
		std::vector<bool> &solutionArguments){

		std::vector<int> componentsList;

		std::unique_ptr<Graph> G = buildSatGraph(listOfHashedLexems, numberOfVariables);
		StronglyComponentsFindClass findingComponentsClass(G->getVertexNum());
		std::unique_ptr<Graph> condensatedGraph = buildingCondenstaionGraph(*G, componentsList);
		if (!existsSatSolution(componentsList)){
			return false;
		}
		topologySortClass DAG;
		DFS(*condensatedGraph, &DAG);
		std::vector<int> vertexCondensatedOrder = DAG.getTopologyOrder();
		std::vector<int> numberOfOrderInCondensation(condensatedGraph->getVertexNum());
		for (size_t currentV = 0; currentV < vertexCondensatedOrder.size(); ++currentV){
			numberOfOrderInCondensation[vertexCondensatedOrder[currentV]] = currentV;
		}
		solutionArguments.resize(numberOfVariables);
		for (int currentArgumentNum = 0; currentArgumentNum < G->getVertexNum(); currentArgumentNum += 2){
			if (numberOfOrderInCondensation[componentsList[currentArgumentNum]] <
				numberOfOrderInCondensation[componentsList[currentArgumentNum + 1]]){
				solutionArguments[currentArgumentNum >> 1] = false;
			}
			else if (numberOfOrderInCondensation[componentsList[currentArgumentNum]] >
				numberOfOrderInCondensation[componentsList[currentArgumentNum + 1]]){
				solutionArguments[currentArgumentNum >> 1] = true;
			}

		}
		return true;
	}
}
